package com.lili.dt;

/**
 * @Auther: 李 力
 * @Date: 2024/8/8
 * @Description: 零钱兑换1
 * @version: 1.0
 */
public class Leetcode322 {

    public static int coinChange(int[] coins, int amount) {
        int[][] dp = new int[coins.length][amount + 1];
        for (int j = 1; j < amount + 1; j++) {
            if (j >= coins[0]) {
                dp[0][j] = dp[0][j - coins[0]] + 1;
            } else {
                dp[0][j] = amount + 1;
            }
        }
        for (int i = 1; i < coins.length; i++) {
            for (int j = 1; j < amount + 1; j++) {
                if (j >= coins[i]) {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - coins[i] + 1]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[coins.length - 1][amount] < amount + 1 ? dp[coins.length - 1][amount] : -1;
    }


    //降维
    public static int coinChange2(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        for (int j = 1; j < amount + 1; j++) {
            if (j >= coins[0]) {
                dp[j] = dp[j - coins[0]] + 1;
            } else {
                dp[j] = amount + 1;
            }
        }
        for (int i = 1; i < coins.length; i++) {
            for (int j = 1; j < amount + 1; j++) {
                if (j >= coins[i]) {
                    dp[j] = Math.min(dp[j], dp[j - coins[i] + 1]);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}
